package com.tucc.hello.leetcode.no1_400.no1_200.no81_100.no97;

/**
 * @author tucc
 * @description todo
 * @package com.tucc.hello.leetcode
 * @date 2021/5/20
 **/
public class Solution2 {

    public static void main(String[] args) {
        Solution2 solution = new Solution2();
        String s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc";
        s1= "abababababababababababababababababababababababababababababababababababababababababababababababababbb";
        s2= "babababababababababababababababababababababababababababababababababababababababababababababababaaaba";
        s3= "abababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababbb";
        System.out.println(solution.isInterleave(s1, s2, s3));
    }

    public boolean isInterleave(String s1, String s2, String s3) {
        return s1.length() + s2.length() == s3.length() && isInterleave(s1, s2, s3, 0, 0, 0);
    }

    public boolean isInterleave(String s1, String s2, String s3, int l1, int l2, int l3) {
        if (l3 == s3.length()) {
            return true;
        }
        if (l1 >= s1.length()) {
            return s2.charAt(l2) == s3.charAt(l3)
                    && isInterleave(s1, s2, s3, l1, l2 + 1, l3 + 1);
        }
        if (l2 >= s2.length()) {
            return s1.charAt(l1) == s3.charAt(l3)
                    && isInterleave(s1, s2, s3, l1 + 1, l2, l3 + 1);
        }
        return (s1.charAt(l1) == s3.charAt(l3)
                && isInterleave(s1, s2, s3, l1 + 1, l2, l3 + 1))
                || (s2.charAt(l2) == s3.charAt(l3)
                && isInterleave(s1, s2, s3, l1, l2 + 1, l3 + 1));
    }

}
